package newcoder

import (
	"sort"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类 the root of binary tree
 * @return int整型二维数组
 */
func threeOrders(root *TreeNode) [][]int {
	// write code here
	var res [][]int
	var pre []int

	res = append(res, preOrder(root, pre))

	var mid []int
	res = append(res, midOrder(root, mid))

	var next []int
	res = append(res, nextOrder(root, next))

	return res
}

func preOrder(root *TreeNode, arr []int) []int {
	if root == nil {
		return arr
	}
	arr = append(arr, root.Val)
	arr = preOrder(root.Left, arr)
	arr = preOrder(root.Right, arr)
	return arr
}

func midOrder(root *TreeNode, arr []int) []int {
	if root == nil {
		return arr
	}
	arr = midOrder(root.Left, arr)
	arr = append(arr, root.Val)
	arr = midOrder(root.Right, arr)
	return arr
}
func nextOrder(root *TreeNode, arr []int) []int {
	if root == nil {
		return arr
	}
	arr = nextOrder(root.Left, arr)
	arr = nextOrder(root.Right, arr)
	arr = append(arr, root.Val)
	return arr
}

/**
 * @description: NC119 最小的K个数
 * @keyword:
 * @author: kami
 * @date 2023/12/10 10:09
 */
func getLeastNumbers_Solution(input []int, k int) []int {
	// write code here
	sort.Ints(input)
	var res []int
	for i := 0; i < k; i++ {
		res = append(res, input[i])
	}
	return res
}

type ListNode struct {
	Val  int
	Next *ListNode
}

/**
 * @description: BM3 链表中的节点每k个一组翻转
 * @keyword:
 * @author: kami
 * @date 2023/12/10 18:42
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
	var tail = head
	for i := 0; i < k; i++ {
		if tail == nil {
			return head
		}
		tail = tail.Next
	}
	var pre *ListNode
	var cur = head
	for cur != tail {
		var temp = cur.Next
		cur.Next = pre
		pre = cur
		cur = temp
	}
	head.Next = reverseKGroup(tail, k)
	return pre
}

/**
 * @description: BM14 链表的奇偶重排
 * @keyword:
 * @author: kami
 * @date 2023/12/11 22:01
 */
func oddEvenList(head *ListNode) *ListNode {
	// write code here
	if head == nil || head.Next == nil {
		return head
	}

	var aHead *ListNode
	var aCur *ListNode
	var bHead *ListNode
	var bCur *ListNode
	var cur = head
	var even = false
	for cur != nil {
		var next = cur.Next
		// 偶数
		if even {
			if bHead == nil {
				bHead = cur
				bCur = cur
			} else {
				bCur.Next = cur
				bCur = cur
				bCur.Next = nil
			}
		} else {
			if aHead == nil {
				aHead = cur
				aCur = cur
			} else {
				aCur.Next = cur
				aCur = cur
				aCur.Next = nil
			}
		}
		even = !even
		cur = next
	}
	if aCur != nil {
		aCur.Next = bHead
	}

	return aHead
}

func preorderTraversal(root *TreeNode) []int {
	// 先序遍历是按照 中 - 左 - 右
	var res []int
	if root == nil {
		return res
	}
	return preorderTraversalDfs(root, res)
}

func preorderTraversalDfs(root *TreeNode, arr []int) []int {
	arr = append(arr, root.Val)
	if root.Left != nil {
		arr = preorderTraversalDfs(root.Left, arr)
	}
	if root.Right != nil {
		arr = preorderTraversalDfs(root.Right, arr)
	}
	return arr
}

var res = make([][]string, 0)

func partition(s string) [][]string {
	// write code here
	var curRes = make([]string, 0)
	backtrack(s, 0, curRes)
	return res
}

func backtrack(s string, start int, curRes []string) {
	if start == len(s) {
		res = append(res, curRes)
		return
	}
	for i := start; i < len(s); i++ {
		if isPlaindrome(s, start, i) {
			curRes = append(curRes, s[start:i+1])
			backtrack(s, i+1, curRes)
			curRes = curRes[0 : len(curRes)-1]
		}
	}

}

func isPlaindrome(s string, start, end int) bool {
	for start < end {
		if s[start] != s[end] {
			return false
		}
		start++
		end--
	}
	return true
}

func partitionII(s string) []string {
	// write code here
	var res = make(map[string]struct{})
	for i := 0; i < len(s); i++ {
		var curRes = expandAroundCenter(s, i, i)
		if len(curRes) > 0 {
			for j := 0; j < len(curRes); j++ {
				if _, ok := res[curRes[j]]; !ok {
					res[curRes[j]] = struct{}{}
				}
			}
		}
		var curRes1 = expandAroundCenter(s, i, i+1)
		if len(curRes1) > 0 {
			for j := 0; j < len(curRes1); j++ {
				if _, ok := res[curRes1[j]]; !ok {
					res[curRes1[j]] = struct{}{}
				}
			}
		}
	}
	var strRes []string
	for s2 := range res {
		strRes = append(strRes, s2)
	}
	sort.Strings(strRes)
	return strRes
}

func expandAroundCenter(s string, left, right int) []string {
	var res []string
	for left >= 0 && right < len(s) && s[left] == s[right] {
		if right > left {

			res = append(res, s[left:right+1])
		}
		left--
		right++
	}
	return res
}

func healthyCows(pasture [][]int, k int) int {
	// write code here
	var sickCows [][2]int
	var leftHealthCnt = 0
	for i := 0; i < len(pasture); i++ {
		for j := 0; j < len(pasture[i]); j++ {
			if pasture[i][j] == 2 {
				sickCows = append(sickCows, [2]int{i, j})
			} else if pasture[i][j] == 1 {
				leftHealthCnt++
			}
		}
	}
	var minutes = 0
	for len(sickCows) > 0 && minutes < k {
		minutes++
		var newSickCows [][2]int
		var size = len(sickCows)
		for i := 0; i < size; i++ {
			sickCow := sickCows[i]
			var x = sickCow[0]
			var y = sickCow[1]

			// 上
			if x-1 >= 0 && pasture[x-1][y] == 1 {
				pasture[x-1][y] = 2
				newSickCows = append(newSickCows, [2]int{x - 1, y})
				leftHealthCnt--
			}
			// 下
			if x+1 < len(pasture) && pasture[x+1][y] == 1 {
				pasture[x+1][y] = 2
				newSickCows = append(newSickCows, [2]int{x + 1, y})
				leftHealthCnt--
			}
			// 左
			if y-1 >= 0 && pasture[x][y-1] == 1 {
				pasture[x][y-1] = 2
				newSickCows = append(newSickCows, [2]int{x, y - 1})
				leftHealthCnt--
			}
			// 右
			if y+1 < len(pasture[x]) && pasture[x][y+1] == 1 {
				pasture[x][y+1] = 2
				newSickCows = append(newSickCows, [2]int{x, y + 1})
				leftHealthCnt--
			}
		}
		sickCows = newSickCows
	}
	return leftHealthCnt
}

func exist(board [][]byte, word string) bool {
	var m = len(board)
	var n = len(board[0])
	var visit = make([][]bool, m)
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			visit[i] = append(visit[i], false)
		}
	}

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if backtrackExist(board, visit, word, i, j, 0) {
				return true
			}
		}
	}
	return false
}

func backtrackExist(board [][]byte, visit [][]bool, word string, i, j, curIdx int) bool {
	if curIdx == len(word) {
		return true
	}

	if i < 0 || i >= len(board) || j < 0 || j >= len(board[i]) || visit[i][j] || curIdx >= len(word) || board[i][j] != word[curIdx] {
		return false
	}

	visit[i][j] = true
	var up = backtrackExist(board, visit, word, i-1, j, curIdx+1)
	if up {
		visit[i][j] = false
		return true
	}
	var down = backtrackExist(board, visit, word, i+1, j, curIdx+1)
	if down {
		visit[i][j] = false
		return true
	}
	var left = backtrackExist(board, visit, word, i, j-1, curIdx+1)
	if left {
		visit[i][j] = false
		return true
	}
	var right = backtrackExist(board, visit, word, i, j+1, curIdx+1)
	if right {
		visit[i][j] = false
		return true
	}
	visit[i][j] = false
	return false
}

var res1 [][]int

func combine(n int, k int) [][]int {
	dfs(n, k, 1, []int{})
	return res1
}

func dfs(n, k, i int, cur []int) {
	if len(cur) == k {
		var curRes = make([]int, len(cur))
		copy(curRes, cur)
		res1 = append(res1, curRes)
		return
	}
	for start := i; start <= n; start++ {
		cur = append(cur, start)
		dfs(n, k, start+1, cur)
		cur = cur[:len(cur)-1]
	}
}

var res2 []string

func letterCasePermutation(s string) []string {
	dfsLetter(s, []byte{}, 0)
	return res2
}

func dfsLetter(s string, cur []byte, start int) {
	if len(cur) == len(s) {
		var temp = make([]byte, len(s))
		copy(temp, cur)
		res2 = append(res2, string(temp))
		return
	}

	for i := start; i < len(s); i++ {
		if isSmallLetter(s[i]) {
			var temp = make([]byte, len(cur))
			copy(temp, cur)

			cur = append(cur, s[i])
			dfsLetter(s, cur, i+1)

			temp = append(temp, s[i]-32)
			dfsLetter(s, temp, i+1)
		} else if isBigLetter(s[i]) {
			var temp = make([]byte, len(cur))
			copy(temp, cur)

			cur = append(cur, s[i])
			dfsLetter(s, cur, i+1)
			temp = append(temp, s[i]+32)
			dfsLetter(s, temp, i+1)
		} else {
			cur = append(cur, s[i])
			dfsLetter(s, cur, i+1)
		}
	}
}

func isSmallLetter(s byte) bool {
	return s-'a' >= 0 && s-'a' <= 25
}
func isBigLetter(s byte) bool {
	return (s-'A' >= 0 && s-'A' <= 25)
}

func cow_permute(nums []int) [][]int {
	var res [][]int

	var cowPermuteDfs = func(nums, cur []int, flags []bool) {}
	cowPermuteDfs = func(nums, cur []int, flags []bool) {
		if len(nums) == len(cur) {
			var temp = make([]int, len(cur))
			copy(temp, cur)
			res = append(res, temp)
			return
		}

		for i := 0; i < len(nums); i++ {
			if !flags[i] {
				cur = append(cur, nums[i])
				flags[i] = true
				cowPermuteDfs(nums, cur, flags)
				cur = cur[:len(cur)-1]
				flags[i] = false
			}
		}
	}
	sort.Ints(nums)
	var flags = make([]bool, len(nums))
	cowPermuteDfs(nums, []int{}, flags)
	return res
}

func findWords(board [][]byte, words []string) []string {
	// write code here
	var find func(board [][]byte, visit [][]bool, word string, i, j, index int) bool
	find = func(board [][]byte, visit [][]bool, word string, i, j, index int) bool {
		if index == len(word) {
			return true
		}
		if i < 0 || i >= len(board) || j < 0 || j >= len(board[i]) || visit[i][j] || board[i][j] != word[index] {
			return false
		}
		visit[i][j] = true
		// 上
		var up = find(board, visit, word, i-1, j, index+1)
		if up {
			return true
		}
		// 下
		var down = find(board, visit, word, i+1, j, index+1)
		if down {
			return true
		}
		// 左
		var left = find(board, visit, word, i, j-1, index+1)
		if left {
			return true
		}
		// 右
		var right = find(board, visit, word, i, j+1, index+1)
		if right {
			return true
		}
		visit[i][j] = false
		return false
	}

	var exit = func(board [][]byte, word string) bool {
		var visit = make([][]bool, len(board))
		for i := 0; i < len(board); i++ {
			visit[i] = make([]bool, len(board[i]))
		}
		for i := 0; i < len(board); i++ {
			for j := 0; j < len(board[i]); j++ {
				if find(board, visit, word, i, j, 0) {
					return true
				}
			}
		}
		return false
	}
	var res []string
	for _, word := range words {
		if exit(board, word) {
			res = append(res, word)
		}
	}
	return res
}

func minPathProduct(cows [][]int) int64 {
	// write code here
	var dp = make([][]int64, len(cows))
	dp[0] = make([]int64, len(cows[0]))
	dp[0][0] = int64(cows[0][0])
	for i := 1; i < len(cows[0]); i++ {
		dp[0][i] = dp[0][i-1] * int64(cows[0][i])
	}
	for i := 1; i < len(cows); i++ {
		dp[i] = make([]int64, len(cows[i]))
		dp[i][0] = dp[i-1][0] * int64(cows[i][0])
	}
	for i := 1; i < len(cows); i++ {
		for j := 1; j < len(cows[i]); j++ {
			dp[i][j] = min(dp[i-1][j], dp[i][j-1]) * int64(cows[i][j])
		}
	}
	return dp[len(cows)-1][len(cows[0])-1]
}

func min(a, b int64) int64 {
	if a > b {
		return b
	}
	return a
}
